package com.lw.leetcode.binary.a;

/**
 * binary
 * 1539. 第 k 个缺失的正整数
 *
 * @Author liw
 * @Date 2021/8/3 21:39
 * @Version 1.0
 */
public class FindKthPositive {

    public static void main(String[] args){
        FindKthPositive test = new FindKthPositive();
        // 输入：arr = [2,3,4,7,11], k = 5   输出：9
//        int[] arr = {2,3,4,7,11};
//        int k = 5;

        // 输入：arr = [1,2,3,4], k = 2   输出：6
//        int[] arr = {1,2,3,4};
//        int k = 2;

        // 输入： 2] 1   1
        int[] arr = {2};
        int k = 1;
        int kthPositive = test.findKthPositive(arr, k);
        System.out.println(kthPositive);
    }

    public int findKthPositive(int[] arr, int k) {
        if (arr[0] > k) {
            return k;
        }
        int st = 0;
        int end = arr.length - 1;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            int c = arr[m] - m - 1;
            if (c < k) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return k  + st  + 1;
    }

}
